1. Field of the Invention
The present invention relates generally to wireless networks with multiple wireless stations (“WSs”) and access-points (“APs”). More specifically, the present invention relates to multi-access wireless networks with a number of data and media applications, including voice applications. Traffic on such a network may be sent over multiple wireless links towards its destination
2. Discussion of the Related Art
In multi-access networks, such as 802.11 networks, inherent inefficiencies exist in channel (medium) access and wireless transport in the lower layers. Often such inefficiencies arise out of the adhoc and multi-access nature of such networks. 802.11 networks are multi-access networks based on a carrier-sense multiple access (CSMA) scheme. In supporting real-time traffic, for example, the CSMA scheme has inefficiencies in the mechanisms in both the medium access control (MAC) and physical (PHY) layers. Such inefficiencies are particularly significant when the data packets have small payloads or have certain statistical characteristics in their real-time behavior. One example is the two-way constant bit-rate transmission of voice (e.g. in a voice over internet protocol (“VoIP”) applications). In VoIP, the voice traffic is transmitted at a bit rate generally of less than 64 kb per second in each direction, with an average packet interval between 10 to 30 milliseconds. In a typical VoIP application, the payload in each data packet varies from a few bytes up to about 240 bytes.
The inefficiencies significantly reduce system throughput or the number of users or calls that can be supported. In the detailed description below, the term “system capacity” refers to both the number of users or calls supported and the system throughput. One source of inefficiency is the MAC-PHY overheads incurred at each access to the medium. For a given bit-rate, a smaller packet size results in more frequent accesses to the wireless medium. Thus, even at maximum inter-packet intervals (e.g., around 30 msec), a single 802.11 access-point with an 11 Mb/s physical layer (PHY) may reach its capacity limit supporting only 13 two-way voice calls, especially when a distributed contention scheme (e.g., the CSMA scheme) is used. For voice traffic under ITU-T Rec G.711, the 11 Mb/s PHY layer achieves only a 0.97 Mb/s (i.e., ((280×8)/0.03)×13=0.97 Mb/s) effective voice payload data transmission rate1, representing an effective capacity utilization rate of 8.82% of the potential 11 Mb/s PHY layer. 1In this example there are also overheads in the 802.11 payload of IP, UDP and RTP headers (40 bytes total).
In a single-user (or single-call) single-hop system, improvement to MAC-PHY layer efficiency is limited. FIG. 1 shows a single mobile terminal (MT) communicating directly with a single gateway access point (GAP). While the MT's MAC-PHY protocol layers and the GAP's MAC-PHY protocol layers include some flow control mechanisms (e.g., buffering and bursting a single flow or performing class differentiation across multiple flows with different priorities), the improvements achieved by such mechanisms are limited. Techniques that are applicable on a per-flow (or per-class-of-flow) basis mitigate short-term traffic fluctuations and favor high-priority flows (with less performance for low-priority flows) under a limited system capacity. Such techniques are primarily concerned with quality-of-service (QoS) tradeoffs between or within flows. These mechanisms are also opportunistic, rather than well-designed processes of general application. To take advantage of a contention-free (burst) MAC/PHY mechanism, for example, the traffic arrivals and channel access opportunities must be well-matched. If a single flow does not have bursty arrival statistics, the burst MAC-PHY mechanism provides no advantage, or works only when the arrival statistics are modified by additional delay elements.
In a multi-user (or multi-flow) multi-hop system with multiple APs, where voice data traverse more than one wireless link (hop), single-user single-flow techniques may still be applicable on a per-user and per-hop basis. Even though such a simple (per-user, per-hop, per-flow) approach has some advantages in system design and complexity, poor performance may result in networks (meshes) of APs interconnected via their wireless interfaces.
A presentation by Locust World in the Voice over Net (VON) Conference held in San Jose during the week of Mar. 7, 2005 disclosed “speech servers” used within a mesh of 802.11 APs. As mentioned above, voice is not known to be friendly traffic for a network. One approach to improve voice traffic performance is to provide substantial radio resources. Alternatively, as disclosed by Locust World's presenter, nodes can act as speech switches to concentrate speech traffic along certain routes, so as to limit the effects that speech may have across the entire network. Such an approach overlays a sub-network within the mesh and concentrates voice traffic to the “speech servers,” Tunneling, which is a form of aggregation, may be used in conjunction with this approach. However, these “speech servers” are static—i.e., the routing does not adapt, nor take advantage of the non-speech server traffic. Nor does the speech servers optimize by using information about the MAC-PHY performance. There is no mention of traffic aggregation for the speech servers.
Packet aggregation alleviates the large header overheads associated with the different layers of the ISO standard. In real-time protocol (RTP) multiplexing, for instance, multiple RTP streams are encapsulated in a single RTP payload, which is then transmitted between two end points (e.g., IP telephony gateways). The Internet draft proposal “Tunneling multiplexed compressed RTP (TCRTP),” available as draft-ietf-avt-tcrtp-08.txt from the internet archive of the Internet Engineering Task Force (IETF), describes improving bandwidth utilization in RTP streams by combining compression, multiplexing, and tunneling protocols over a network path. Compression reduces the IP/UDP/RTP header overhead of a single RTP stream. Tunneling transports compressed headers and payloads through a multi-hop IP network, without having to decompress and re-compress at every link. Multiplexing reduces the tunnel headers overhead by amortizing a single tunnel header over many RTP payloads. Using that method, multiple RTP streams are multiplexed into a single RTP packet until either a predetermined packet size (in number of bytes or number of payloads) is reached, or a timer expires. The optimal value for the packet size or the timer duration depends upon the required data rate and the acceptable delay in the network. Similar flow aggregation techniques are used in VoIP over ATM networks (“VoATM”) and VoIP over MPLS (“VoMPLS”) networks. Because voice packets can be very small (e.g., a few bytes) and ATM cells have a minimum size (i.e., 48 bytes), multiplexing voice packets into a single ATM cell improves bandwidth utilization. Up to now, however, RTP multiplexing is limited to single-destination hosts within a wired IP network
The paper entitled “Solutions to performance problems in VoIP over a 802.11 wireless LAN,” by W. Wang, S. C. Liew, and V. O. K. Li, in the IEEE Transactions on Vehicular Technology, Vol. 54, No. 1, January 2005, addresses low capacity in wireless 802.11 networks. The authors propose to multiplex downlink voice streams at a voice gateway into a single larger packet, which is then multicast to all receivers in a single transmission. FIG. 2 illustrates their proposed solution. In this proposed solution, security is achieved by encrypting the voice packets. The multiplexer replaces the IP/UDP/RTP header of each voice packet by a compressed mini-header that identifies the RTP session with a packet identifier (ID). Each receiver uses the packet ID to extract its voice packets from the multiplexed packet and restores the original headers.
The multiplex-multicast approach also solves the asymmetry problem between uplink and downlink communications in the last hop (i.e., the AP does not have to contend for the channel at least as many times as there are voice packets to transmit). However, this solution is not readily applicable to a multi-hop wireless network, as no broadcast takes place at the intermediate hops. The intermediate hops are often where bottlenecks occur. Calls may be forwarded through one or several relay nodes (access points or wireless routers) before reaching the voice gateway and other local calls may try to connect to the APs along the way. With multiple APs transmitting to the gateway, congestion can quickly build up. Multicast techniques are not applicable to multi-hop networks and are generally downlink-only mechanisms at terminating links.
Proposals for frame aggregation at the MAC/PHY layers of a wireless medium and for capacity-increasing bursting mechanisms have been received at Task Group N (TGn) of the 802.11 Standard. One proposal from Worldwide Spectrum Efficiency (WWiSE) aggregates frames at the PHY layer using signal fields to separate multiple MAC Protocol Data Units (MPDUs) within a PLCP Protocol Data Unit (PPDU). WWiSE also recommends using a bursting mechanism within the 802.11e Standard, where PPDUs are sent in succession on the wireless channel within RIFSs (reduced inter-frame spaces) of each other. A proposal from the TGn Sync Group (TGnSync) conducts frame aggregation at the MAC layer or at the interface between the MAC and the PHY layers. Under that proposal, MPDUs are aggregated into one PLCP Service Data Unit (PSDU) with MPDU delimiters located at the beginning of each MPDU. The proposal also aggregates multiple MAC Service Data units (MSDUs) into one MSDU, to allow sharing of the MAC header and the CRC bits. The WWiSE and TGnSync proposals improve MAC and PHY layer (i.e., Layer 2) efficiency.
Some additional mechanisms are used in the MAC-PHY layers. For example existing 802.11a/b/g systems do not aggregate payloads within the MAC-PHY layers. For a large payload that exceeds the MAC payload limit, a segregation or fragmentation algorithm transmits fragments of the payload onto the wireless channel in a bursty fashion separated by small inter-frame space (SIFS) intervals. The 802.11e standard has a bursting mechanism at RIFS intervals used during contention periods. The bursting mechanism is limited, however, to transmitting fragments of the same MSDU.
As with the multiplex-multicast approach, these mechanisms fall into the class of per-hop techniques and while they can help performance in multi-hop scenarios by improving the efficiency of individual links, they do not fully address issues or potential improvements that can occur in multi-hop environments.
There is also work on improving performance in multi-hop scenarios. However, earlier wireless multi-hop routing protocols, such as (AODV, DSR, DSDP, TORA), treat the routing problem independently from the lower (e.g. MAC/PHY) layers. These protocols perform path discovery in a best-effort fashion, without guarantees or consideration for system performance or Quality of Service (QoS). These protocols serve mainly mobile ad-hoc networks (MANET), where finding a connected path has high priority. However, modem networks are primarily static (i.e., wireless relays are stationary and connectivity is guaranteed). More importantly, 802.11 networks have high overhead and routing protocols that do not address these overheads have poor system performance. Some networks incorporate path cost metrics to measure the insufficient resources in the lower layers, and make routing decisions according to the metrics.
More recently, some researchers consider routing in wireless networks in conjunction with resource allocation in lower layers. The result is a combined routing and MAC/PHY layer mechanism that provides optimal network operations. Similar approaches are also used in wireless sensor networks, which are more application-specific and amenable to further optimization. However, many of these routing algorithms rely on assumptions that are not applicable to 802.11 protocols.
Existing solutions do not exploit the operational capacity of 802.11 networks. Transport capacity of 802.11 is highly inefficient because each packet has contention, transmission and acknowledgement overheads.